package com.example.demo.arithmetic.datastructure.tree;

import java.util.LinkedList;

/**
 * 后序优先遍历 计算最大深度
 * 二叉树最大深度
 * 给定一个二叉树 root ，返回其最大深度。
 * <p>
 * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
 */
public class Leetcode104_2 {


    public int maxDepth(TreeNode node) {
        TreeNode curr = node;
        TreeNode pop = null;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int maxHeight = 0;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                if (stack.size() > maxHeight) {
                    maxHeight = stack.size();
                }
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                } else {
                    curr = peek.right;
                }
            }
        }
        return maxHeight;
    }
}
